/**
 * 归并排序
 *      算法思想：通过 递归 将 长度为n 的列表分成 n 个 （只有一个元素） 的有序列表，
 *      然后通过 合并有序表的 算法，对 n 个有序列表进行 合并
 *      第一次合并后 生成 n/2 个 有序表
 *      第二次合并后 生成  n/2/2 个有序表
 *      直到 合成一个 大的有序表时结束
 * @param {*} list 需要排序的数据
 * @param {*} tmpList 用于临时装载元素的列表
 * @param {*} left 因为实在 一个 列表内完成排序的，所以需要 左右指针 来划分区域
 */
function mergeSort (list, tmpList, left, right) {
    if (left < right) {
        let center = Math.floor((left + right)/2)
        mergeSort(list, tmpList, left, center)
        mergeSort(list, tmpList, center + 1, right)
        merge(list, tmpList, left, center + 1, right)
    }
}


/**
 * 
 * @param {*} list 
 * @param {*} tmpList 
 * @param {*} left 
 * @param {*} right 
 * @param {*} rightEnd 
 */
function merge (list, tmpList, left, right, rightEnd) {
    let leftEnd = right - 1,tmpPos = left,tmpLength = rightEnd - left + 1,i
    while (left <= leftEnd && right <= rightEnd) {
        if (list[left] <= list[right]) {
            tmpList[tmpPos++] = list[left++] 
        } else {
            tmpList[tmpPos++] = list[right++]
        }
    }
    while (left <= leftEnd) {
        tmpList[tmpPos++] = list[left++]
    }
    while (right <= rightEnd) {
        tmpList[tmpPos++] = list[right++]
    }
    // 把排序好的内容写回列表中
    for (i = 0; i < tmpLength; i++, rightEnd--) {
        list[rightEnd] = tmpList[rightEnd]
    }
}

let data = [0,2,4,6,1,3,5,7,9,11,8,10,12]
let tmp = []
mergeSort(data, tmp, 0, data.length - 1)
console.log(tmp)